package main

func main() {
	
}

//#link: https://leetcode-cn.com/problems/remove-invalid-parentheses/
/**
 * @Description: 判断字符串是否为有效括号
 */
func isValid(str string) bool {
	cnt := 0
	for _, ch := range str {
		if ch == '(' {
			cnt++
		} else if ch == ')' {
			cnt--
			if cnt < 0 {
				return false
			}
		}
	}
	return cnt == 0
}

/**
 * @Description: 回溯判断追寻结果集
 */
func helper(ans *[]string, str string, start, lcount, rcount, lremove, rremove int) {
	// 当要移除的左右括号数量同时为0的时候，对字符串进行有效判断
	if lremove == 0 && rremove == 0 {
		if isValid(str) {
			*ans = append(*ans, str)
		}
		return
	}

	for i := start; i < len(str); i++ {
		// 重复的括号则跳过 , 例如 "((())" ，最终结果都会为 (())
		if i != start && str[i] == str[i-1] {
			continue
		}
		// 如果剩余的字符无法满足去掉的数量要求，直接返回
		if lremove+rremove > len(str)-i {
			return
		}
		// 尝试去掉一个左括号
		if lremove > 0 && str[i] == '(' {
			helper(ans, str[:i]+str[i+1:], i, lcount, rcount, lremove-1, rremove)
		}
		// 尝试去掉一个右括号
		if rremove > 0 && str[i] == ')' {
			helper(ans, str[:i]+str[i+1:], i, lcount, rcount, lremove, rremove-1)
		}
		if str[i] == ')' {
			lcount++
		} else if str[i] == ')' {
			rcount++
		}
		// 当前右括号的数量大于左括号的数量则为非法,直接返回.
		if rcount > lcount {
			break
		}
	}
}

/**
 * @Description: 移除无效的括号
 */
func removeInvalidParentheses(s string) (ans []string) {
	// 要移除的左,右括号数量
	lremove, rremove := 0, 0
	for _, ch := range s {
		// 左括号++
		if ch == '(' {
			lremove++
		} else if ch == ')' {
			// 当左括号数量为0时，则右括号 ++，否则左括号 --
			if lremove == 0 {
				rremove++
			} else {
				lremove--
			}
		}
	}

	helper(&ans, s, 0, 0, 0, lremove, rremove)
	return
}

